字典樹(trie)是一種樹狀資料結構，用於儲存關聯有序陣列，通常是字串。(圖1)其在儲存與搜尋字串方面在空間與時間上很有效率。其任一節點可以字典的形式儲存非重複地任意字元和其指向下個節點的訊息。(圖2)每個node有attribute判斷是不是字串的結尾(end of string)。實際應用的例子，像是auto completion(輸入字串的部分內容，自動推薦相關字串)或是拼字檢查(spell checking)。

圖1 trie 示意圖，每個節點可以儲存多個字元(key)，每個字元會指向下一個字元(value)，以字典的形式儲存，最後的字元會指向字元的結尾。(對字典不熟的，可以複習一下第三天的文章)

圖2 這裡以插入CAT和CAKE在trie裡為例子，展示trie資料結構的儲存方法。

圖3 再舉個例子，這裡插入APP和APPLE在TRIE裡。
以下直接來看程式碼:

# 用dictionary建立trie node，並給它一個attribute叫endofstring
class TrieNode:
    def __init__(self):
        self.children = {}
        self.endofstring = False

class Trie:
    # 初始化trie
    # 時間複雜度: O(1)， 空間複雜度: O(1)
    def __init__(self):
        self.root = TrieNode()
        
    # 插入字元，這裡我們找我們所建的dictionary是否已經有這個字元了，有個話直接前往字元連結到的那個dictionary,當全部結束，將那個dictionary的endofstring設為True
    #時間複雜度:O(m)， 空間複雜度:O(m)，m為字元長度
    def insertWord(self, word):
        current = self.root
        for ch in word:
            Node = current.children.get(ch)
            if Node is None:
                Node = TrieNode()
                current.children.update({ch: Node})
            current = Node
        current.endofstring = True
        return 'Successfully insert a node!'
    #搜索字元是否存在於Trie中
    #時間複雜度:O(m)， 空間複雜度:O(1)
    def searchWord(self, target):
        current = self.root
        for ch in target:
            Node = current.children.get(ch)
            if Node is None:
                return False
            else:
                current = Node
        if current.endofstring == True:
            return True
        else:
            return False

刪除字串的部分相較於插入就比較複雜，需要考慮到幾種情況，1.節點(dictionary)是否和其他字元共用"有的話，len(currentNode.children)>1，這種情況下，節點不能刪，但可以刪除字典裡面的字元 2.字元和其他字串共用(e.g.CAKE和CAT)，3.其中一個字串是另一個字串的prefix(前贅)(e,g,APPLE 和APP)。下面我們直接看程式碼:

# 時間複雜度: O(m)，空間複雜度: O(1)
def deleteString(root, word, index):
    ch = word[index]
    currentNode = root.children.get(ch)
    canThisNodeBeDeleted = False
    if len(currentNode.children) > 1:
        deleteString(currentNode, word, index+1)
        return False

    if index == len(word) - 1:
        if len(currentNode.children) >= 1:
            currentNode.endofstring = False
            return False
        else:
            root.children.pop(ch)
            return True

    if currentNode.endofstring == True:
        deleteString(currentNode, word, index+1)
        return False

    canThisNodeBeDeleted = deleteString(currentNode, word, index+1)
    if canThisNodeBeDeleted == True:
        root.children.pop(ch)
        return True
    else:
        return False

參考資料:
The Complete Data Structures and Algorithms Course in Python (udemy)